昨天我們介紹單向鏈結串列(singly linked list)，不同於單向鏈結串列，雙向鏈結串列(doubly linked list)的每個節點會也多一個指標指向前一個節點，如圖。

下面直接來看一下程式碼:
Singly Doubly linked list

class Node:
    def __init__(self,value=None):
        self.value=value
        self.next=None
        self.prev=None
        
class doubly_linked_list:
    def __init__(self):
        self.head=None
        self.tail=None
        
    #print function-time complexity: O(n), Space complexity: O(1)
    def __str__(self):
        result=''
        temp_node=self.head
        while temp_node:
            result+=str(temp_node.value)
            if temp_node==self.tail:
                break
            else:
                result+='<->'
                temp_node=temp_node.next
        return result
    
    # time complexity: O(1), space complexity: O(1)
    def append(self,value):
        new_node=Node(value)
        if self.head==None:
            self.head=new_node
            self.tail=new_node
        else:
            self.tail.next=new_node
            new_node.prev=self.tail
            self.tail=new_node

    # time complexity: O(1), space complexity: O(1)       
    def prepend(self,value):
        new_node=Node(value)
        if self.head==None:
            self.head=new_node
            self.tail=new_node
        else: 
            new_node.next=self.head
            self.head.prev=new_node
            self.head=new_node
    
    # time complexity: O(n), space complexity: O(1)
    def traverse(self):
        if self.head==None:
            return 'The Linked List is empty'
        else:
            temp_node=self.head
            while temp_node:
                print(temp_node.value)
                temp_node=temp_node.next
                
    # time complexity: O(n), space complexity: O(1)
    def search(self,target):
        if self.head==None:
            return 'The Linked List is empty'
        else:
            temp_node=self.head
            index=0
            while temp_node:
                if temp_node.value==target:
                    return index
                else:
                    index+=1
                    temp_node=temp_node.next
            return 'Your target is not in the list'
    
    #time complexity: O(n), space complexity: O(1)
    def insert(self,index,value):
        if self.head==None:
            return 'The linked list is empty'
        elif index==0:
            self.prepend(value)
            return 'The value is inserted'
        elif index==-1:
            self.append(value)
            return 'The value is inserted'
        else:
            new_node=Node(value)
            temp_node=self.head
            for _ in range(index-1):
                temp_node=temp_node.next
            new_node.prev=temp_node
            new_node.next=temp_node.next
            temp_node.next.prev=new_node
            temp_node.next=new_node
    
    # time complexity: O(1), space complexity: O(1)
    def pop_first(self):
        if self.head==None:
            return 'The linked list is empty'
        else:
            popped_value=self.head.value
            self.head.next.prev=None
            self.head=self.head.next
            return popped_value
    # time complexity: O(1), space complexity: O(1)
    def pop(self):
        if self.head==None:
            return 'The linked list is empty'
        else:
            popped_value=self.tail.value
            self.tail.prev.next=None
            self.tail=self.tail.prev
            return popped_value
    
    #time complexity: O(n), space complexity: O(1)
    def set_value(self,index,value):
        if self.head==None:
            return 'The linked list is empty'
        else:
            temp_node=self.head
            loc=0
            while temp_node:
                if loc==index:
                    temp_node.value=value
                    return 'The value is set'
                else:
                    index+=1
                    temp_node=temp_node.next
            return 'The index is out of range'
    
    #time complexity: O(n), space complexity: O(1)
    def remove(self,index):
        if self.head==None:
            return 'The linked list is empty'
        elif index==0:
            self.pop_first()
        elif index==-1:
            self.pop()
        else:
            temp_node=self.head
            for _ in range(index-1):
                temp_node=temp_node.next
            if temp_node.next:
                temp_node.next=temp_node.next.next
                temp_node.next.prev=temp_node
                return 'The item is removed'
            else:
                return 'The index is out of range'
            
    # time complexity: O(n), space complexity: O(1)
    def deleteall(self):
        if self.head==None:
            return 'The linked list is empty'
        else:
            temp_node=self.head
            while temp_node:
                temp_node.prev=None
                temp_node=temp_node.next
            self.tail=None
            self.head=None
            return 'The linked list is empty'     

DLL=doubly_linked_list()
DLL.append(10)
DLL.append(20)
DLL.append(30)
print(DLL)
DLL.prepend(50)
print(DLL)
DLL.insert(0,60)
print(DLL)
DLL.insert(3,90)
print(DLL)
DLL.insert(5,100)
print(DLL)
>> 10<->20<->30
>> 50<->10<->20<->30
>> 60<->50<->10<->20<->30
>> 60<->50<->10<->90<->20<->30
>> 60<->50<->10<->90<->20<->100<->30

print(DLL.pop_first())
print(DLL)
print(DLL.pop())
print(DLL)
>> 60
>> 50<->10<->90<->20<->100<->30
>> 30
>> 50<->10<->90<->20<->100

DLL.deleteall()
>> 'The linked list is empty'

Circular Doubly linked list (環狀雙向鏈結)

class Node:
    def __init__(self,value=None):
        self.value=value
        self.next=None
        self.prev=None
        
class circular_doubly_linked_list:
    def __init__(self):
        self.head=None
        self.tail=None
        
    def __str__(self):
        result=''
        temp_node=self.head
        while temp_node:
            result+=str(temp_node.value)
            if temp_node is self.tail:
                return result
            else:
                result+='<->'
                temp_node=temp_node.next
        return result
    
    # time complexity: O(1), space complexity: O(1)
    def append(self,value):
        new_node=Node(value)
        if self.head==None:
            self.head=new_node
            self.tail=new_node
        else:
            self.tail.next=new_node
            new_node.prev=self.tail
            new_node.next=self.head
            self.tail=new_node
            
    # time complexity: O(1), space complexity: O(1)
    def prepend(self,value):
        new_node=Node(value)
        if self.head==None:
            self.head=new_node
            self.tail=new_node
        else:
            new_node.next=self.head
            new_node.prev=self.tail
            self.tail.next=new_node
            self.head.prev=new_node
            self.head=new_node
            
    #time complexity: O(n), space complexity: O(1)
    def traverse(self):
        if self.head==None:
            return 'There is no element is the list'
        else:
            temp_node=self.head
            while temp_node:
                print(temp_node.value)
                if temp_node==self.tail:
                    break
                else:
                    temp_node=temp_node.next
                    
    #time complexity: O(n), space complexity: O(1)
    def search(self,target):
        if self.head==None:
            return 'There is no element in the list'
        else:
            temp_node=self.head
            index=0
            while temp_node:
                if temp_node.value==target:
                    return index
                elif temp_node==self.tail:
                    break
                else:
                    index+=1
                    temp_node=temp_node.next
            return 'There is no such target in the list'
        
    #time complexity: O(n), space complexity: O(1)
    def set_value(self,index,value):
        if self.head==None:
            return 'There is no element in the list'
        elif index==-1:
            self.tail.value=value
            return 'The value is set'
        else:
            temp_node=self.head
            loc=0
            while temp_node:
                if loc==index:
                    temp_node.value=value
                    return 'The value is set'
                elif temp_node==self.tail:
                    break
                else:
                    loc+=1
                    temp_node=temp_node.next
            return 'The index is out of range'
        
    #time complexity: O(n). space complexity: O(1)
    def insert(self,index,value):
        if self.head==None:
            return 'There is no element in the list'
        else:
            new_node=Node(value)
            temp_node=self.head
            if index==0:
                self.prepend(value)
            elif index==-1:
                self.append(value)
            else:
                for _ in range(index-1):
                    temp_node=temp_node.next
                    if temp_node==self.head:
                        return 'The index is out of range'
                if temp_node==self.tail:
                    self.append(value)
                else:
                    new_node.prev=temp_node
                    new_node.next=temp_node.next
                    temp_node.next.prev=new_node
                    temp_node.next=new_node
                return 'Successfully insert the value'
            
    #time complexity: O(1), space complexity: O(1)
    def pop(self):
        if self.head==None:
            return 'There is no element in the list'
        else:
            popped_value=self.tail.value
            self.tail.prev.next=self.head
            self.head.prev=self.tail.prev
            self.tail=self.tail.prev
            return popped_value
        
    #time complexity: O(n), space complexity: O(1)
    def pop_first(self):
        if self.head==None:
            return 'There is no element in the list'
        else:
            popped_value=self.head.value
            self.tail.next=self.head.next
            self.head.next.prev=self.tail
            self.head=self.head.next
            return popped_value
        
    #time complexity: O(n), space complexity: O(1)
    def remove(self,index):
        if self.head==None:
            return 'There is no element in the list'
        elif index==0:
            self.pop_first()
        elif index==-1:
            self.pop()
        else:
            temp_node=self.head
            for _ in range(index-1):
                temp_node=temp_node.next
                if temp_node==self.head:
                    return 'The index is out of range'
                elif temp_node==self.tail:
                    self.pop()
                else:
                    pass
            temp_node.next=temp_node.next.next
            temp_node.next.prev=temp_node
            
    #time complexity: O(n), space complexity: O(1)
    def deleteall(self):
        if self.head==None:
            return 'The list is empty'
        else:
            temp_node=self.head
            while temp_node is not self.tail:
                temp_node.prev=None
                temp_node=temp_node.next
            self.head=None
            self.tail=None
            return 'Successfully delete the list!'
  
CDLL=circular_doubly_linked_list()
CDLL.append(50)
CDLL.append(60)
CDLL.append(70)
print(CDLL)
CDLL.prepend(90)
CDLL.prepend(100)
print(CDLL)
>> 50<->60<->70
>> 100<->90<->50<->60<->70

其他的功能就大家自己試試吧~~感覺資料結構這類的東西都需要自己寫一遍才比較有感覺~

參考資料:
The Complete Data Structures and Algorithms Course in Python (Udemy)